The synthesis of realistic images in three dimensional computer graphics requires the evaluation of a shading model simulating the propagation of light within a scene or environment. Synthesis of realistic shading, and hence of realistic images, requires the use of a global illumination model in which all illumination in the scene, both from direct lighting and reflected light, is taken into account. Shadowing provided by surfaces between the light sources (both direct and reflected light) must also be determined and taken into account to synthesize a realistic image. In the prior art, this process, known as shadow testing, has been time consuming since all points in the scene must be tested against all objects to determine which objects actually shadow the points.
A number of global illumination techniques for generating realistically shaded three dimensional graphics are known, the most common of which are ray tracing and radiosity. The following publications, which are incorporated herein by reference, are illustrative: Goral, Cindy M. et al. "Modeling the Interaction of Light Between Diffuse Surfaces", Computer Graphics, vol. 18, no. 3, pp. 213-222 (July, 1984); Cohen, Michael F. et al., "The HemiCube: A Radiosity Solution For Complex Environments", SIGGRAPH Proceedings, vol. 19, no. 3, pp. 31-40 (1985); Greenberg, Donald P. et al. "Radiosity: A Method For Computing Global Illumination", The Visual Computer, vol. 2, pp. 291-297 (1986); Cohen, Michael F. et al., "An Efficient Radiosity Approach For Realistic Image Synthesis", IEEE CG&A, pp. 26-35 (March, 1986); Cohen Michael F. et al., "A Progressive Refinement Approach to Fast Radiosity Image Generation", Computer Graphics, vol. 22, no. 4, pp. 75-84 (August, 1988). See also the following publications, incorporated herein by reference, which describe various ray tracing techniques: Maxwell, Gregory M. et al., "Calculation of the Radiation Configuration Using Ray Casting", Computer Aided Design, vol. 18, no. 7, pp. 371-379 (September 1986); Arvo, James, "Backward Ray Tracing", Apollo Computer, Inc. Chelmsford, Mass. (date unknown); Cook, Robert L. et al., "Distributed Ray Tracing", Computer Graphics, vol. 18, no. 3, pp. 137-145 (July, 1984); Chattopadhyay, Sudeb et al., "Bi-Directional Ray Tracing", Proceedings of Computer Graphics 1987, pp. 335-343 (1987).
In ray tracing techniques in particular, shadow testing is normally the most computationally expensive process. The reason for this is that each object in the entire environment (scene) must be tested to determine if it occludes each light source (both direct and reflected) for every ray intersection point. For scenes with complex lighting schemes, the percentage of time required for occlusion testing (i.e., shadow testing) can increase to over 80% of the total computation time. This is also true of radiosity techniques that employ ray tracing to compute the form factors employed by radiosity. See, e.g., commonly assigned co-pending U.S. application Ser. No. 088,392 filed Jul. 6, 1993, a continuation of Ser. No. 531,377 filed May 31, 1990, now abandoned entitled "Three Dimensional Computer Graphics Employing Ray Tracing to Compute Form Factors in Radiosity"; see also, Wallace, John R. et al., "A Ray Tracing Algorithm For Progressive Radiosity", Computer Graphics, Vol. 23, no. 3 (pp. 315-324) (July, 1989).
Attempts have been made in the prior art to reduce the time necessary for shadow testing. See, e.g., Haines, Eric A. et al., "The Light Buffer: A Shadow-Testing Accelerator", IEEE CG&A, pp. 6-11, September, 1986. This document discloses a method for reducing shadow testing time in ray tracing techniques by generating light buffers, each of which partition the environment with respect to an individual light source. These partition descriptions are then used during shadow testing to quickly determine a small subset of objects that may have to be tested for intersection. See also, Reeves, William T. et al., "Rendering Antialiased Shadows With Depth Maps", Computer Graphics, Vol. 21, no. 4, pp. 283-291 (July, 1987) which is directed to aliasing problems for shadow algorithms that use depth maps. However, the solution discussed in this document is also expensive to implement, both in terms of required processing time and required memory space.
It is therefore desirable to provide a shadow testing method that is fast and inexpensive in terms of required memory, particularly for complex scenes. It is also desirable that the method not exhibit aliases and artifacts, and that visibility determination of points within the scene be accurate to the tolerance of floating point numbers. The present invention achieves these goals.